package uf;

/**
 *
 * unionElements 操作是O(n)的复杂度, 性能是不够的.
 * 优化 find() isConnected() unionElements() 操作都是 O(h) 复杂度
 *
 */
public class QuickUnion implements UF{

    private int[] parent;

    public QuickUnion(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++)
            parent[i] = i;
    }

    // 返回p元素对应的集合id
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");
        while (p != parent[p]) p = parent[p];
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p); // p元素根节点索引
        int qRoot = find(q); // q元素根节点索引
        if (pRoot == qRoot) return;
        parent[pRoot] = qRoot; // p元素的根节点连接到q元素根节点
    }

    @Override
    public int size() {
        return parent.length;
    }
}
